Частина 2. Методичні вказівки щодо використання функцій алгебри логіки та мінімізації цих функцій у базисі Буля
2.1 Функціональна повнота системи функцій алгебри логіки і наборів логічних елементів
Основна вимога, яка ставиться до набору логічних елементів, полягає в тому, щоб за допомогою цього набору можна було побудувати будь-яку логічну схему. З огляду на те, що функціонування елементів однозначно описується функціями алгебри логіки (ФАЛ), застосовуючи операцію суперпозиції, можна з деякої системи ФАЛ отримати будь-яку, скільки завгодно складну ФАЛ. Тоді ця деяка система ФАЛ буде називатися функціонально повною (ФПС ФАЛ).
Функціонально повним є такий набір ФАЛ, який містить хоча б одну функцію, яка:
не зберігає константу "0";
не зберігає константу "1";
не є монотонною;
не є самодвоїстою;
не є лінійною.
Якщо функція F на нульовому наборі змінних дорівнює 0, тобто F(0,0,...,0)=0, то ця функція зберігає константу "0".
Таблиця 2.1.1
┌──┬────┬────────────────┬──────────────┬─────────┐
│х0 │0011│Назва ФАЛ │ Вираз ФАЛ │ Клас │
│х1 │0101│ │ ├─┬─┬─┬─┬─┤
│ │ │ │ │0│1│Л│М│С│
├──┼────┼────────────────┼──────────────┼─┼─┼─┼─┼─┤
│F0 │0000│константа "0" │0 │X│ │X│X│ │
│F1 │0001│кон'юнкція, І │х0·х1 │X│Х│ │X│ │
│F2 │0010│заборона по х1 │х0·/х1 │X│ │ │ │ │
│F3 │0011│х0 │х0 │X│Х│Х│Х│Х│
│F4 │0100│заборона по х0 │/х0·х1 │X│ │ │ │ │
│F5 │0101│х1 │х1 │X│Х│Х│Х│Х│
│F6 │0110│сума за mod 2 │х0·/х1 v /х0·х1│X│ │Х│ │ │
│F7 │0111│диз'юнкція, АБО │х0 v х1 │X│Х│ │Х│ │
│F8 │1000│АБО-НЕ (Пірса) │/(х0 v х1) │ │ │ │ │ │
│F9 │1001│рівнозначність │х0·х1 v /х0·/х1│ │Х│Х│ │ │
│F10│1010│інверсія х1 │/х1 │ │ │Х│ │Х│
│F11│1011│імплікація звор.│х0 v /х1 │ │Х│ │ │ │
│F12│1100│інверсія х0 │/х0 │ │ │Х│ │Х│
│F13│1101│імплікація пряма│/х0 v х1 │ │Х│ │ │ │
│F14│1110│І-НЕ (Шефера) │/(х0·х1) │ │ │ │ │ │
│F15│1111│константа "1" │1 │ │Х│Х│Х│ │
└──┴────┴────────────────┴──────────────┴─┴─┴─┴─┴─┘
Якщо функція F на одиничному наборі змінних дорівнює 1, тобто F(1,1,...,1)=1, то ця функція зберігає константу "1".
ФАЛ називається монотонною, якщо при будь-якому зростанні кількості "1" у послідовності сусідніх (тобто таких, які відрізняються тільки в одному розряді) наборів змінних (х0,х1,...,xn) значення функції не зменшується.
ФАЛ називається самодвоїстою, якщо на кожній парі протилежних наборів (x0,x1,...,xn) та (/x0,/x1,...,/xn) вона приймає протилежні значення, тобто, якщо виконується умова F(x0,x1,...,xn) = /F(/x0,/x1,...,/xn), де знаком "/" позначена операція інверсії.
ФАЛ називається лінійною, якщо її можна зобразити поліномом Жегалкіна без добутків змінних
F(x0,x1,...,xn) = a0·x0 # a1·x1 # ... # an·xn,
де ai = (0, 1);
· - позначення операції І;
Таблиця
2.1.2
┌───┬─┐
│abc│f│
├───┼─┤
│000│1│
│001│0│
│010│1│
│011│1│
│100│0│
│101│0│
│110│1│
│111│0│
└───┴─┘
# - позначення операції "додавання за модулем 2".
Для того щоб записати функцію, яка задана таблично, у вигляді полінома Жегалкіна, досить записати цю функцію у вигляді суми за модулем 2 тих наборів аргументів, на яких функція дорівнює 1. Після цього потрібно всі змінні, які входять до отриманого виразу з інверсіями, замінити за допомогою співвідношення /х = х # 1, розкрити дужки і звести подібні члени за допомогою тотожності
х # х # ... # х = х, якщо кількість х непарна;
х # х # ... # х = 0, якщо кількість х парна.
У табл. 2.1.1 наведені функції двох змінних і вказаний клас кожної ФАЛ. У графі "Клас" позначено:
0 - зберігає константу "0";
1 - зберігає константу "1";
Л - лінійна;
М - монотонна;
С - самодвоїста.
Приклад 2.1.1. Перевірити, чи створює функція трьох змінних, яка задана табл. 2.1.2, функціонально повну систему.
1) Оскільки на нульовому наборі f(0,0,0) = 1, то ця функція не зберігає константу "0".
2) Оскільки на одиничному наборі f(...
